package com.itheima;

public class Demo4 {

    public static void main(String[] args) {
        int[] a = {12, 20, 5, 16, 15, 1, 30, 45, 23, 9, 4, 4};
        int min = 0;
        int max = a.length - 1;
        sort(a, min, max);
        for (int i : a) {
            System.out.println(i);
        }

    }

    public static void sort(int a[],int min,int max) {
        int key=a[min];//准基数
        int start=min; //开始位置
        int end =max;//结束位置

        while(end>start) {  //循环条件是否数值交叉
            //从后开始往前查找
            while(end>start&&a[end]>=key) {
                //如果找到的值大于基数值，那么继续往下找，end--
                end--;
            }
            //如果找到的值小于基数值，那么进行值交换
            if(a[end]<key) {
                int i=a[end];
                a[end]=a[start];
                a[start]=i;

            }
            //从前往后找
            while(end>start&&a[start]<=key) {
                //如果找到的值小于基数值，那么继续往下找，start++
                start++;
            }
            //如果找到的值大于基数值，那么进行值交换
            if(a[start]>key) {
                int i=a[start];
                a[start]=a[end];
                a[end]=i;

            }
        }

        //这部分的数据都是小于准基数，通过递归在进行一趟快排
        if(start>min) {
            sort(a, min, start-1);  //开始位置为第一位，结束位置为关键索引-1
        }

        if(end<max) {
            sort(a, end+1, max);  //开始位置为关键索引+1，结束位置最后一位
        }




    }

}
